package com.story.framework.core.utils.Hot100.java;


/**
 * @Author: Xiaohei
 * @CreateTime: 2022/2/15 20:24
 */
public class MedianOfTwoSortedArrays {

    public static void main(String[] args) {
        int[] n1 = {1,3,6,7};
        int[] n2 = {0};
        double v = findMedianSortedArrays(n1, n2);
        System.out.println(v);
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.8 MB, 在所有 Java 提交中击败了16.80%的用户
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int lp = 0;
        int rp = 0;
        int l1 = nums1.length;
        int l2 = nums2.length;
        int n = l1 + l2;
        double ans = 0.0;
        int index = 0;
        double current = 0;
        double prev = 0;
        while (index <= n / 2) {
            if (lp >= l1) {
                prev = current;
                current = nums2[rp];
                rp++;
                index++;
                continue;
            }
            if (rp >= l2) {
                prev = current;
                current = nums1[lp];
                lp++;
                index++;
                continue;
            }
            if (nums1[lp]<=nums2[rp]) {
                prev = current;
                current = nums1[lp];
                lp++;
            }else {
                prev = current;
                current = nums2[rp];
                rp++;
            }
            index++;
        }
        ans = n%2==0?(prev + current) / 2:current;
        return ans;
    }
}
